import java.util.Arrays;

public class TestHeap {
    private int[] elem;
    private int usedSize;//有效元素个数

    public TestHeap(){
        this.elem = new int[10];//默认容量为10
    }

//    用于初始化elem数组
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    // 打印堆的内容
    public void printHeap() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

//    将完全二叉树创建成大根堆
//    使用向下调整创建大根堆  时间复杂度为 O(N).
    public void createMaxHeap(){
        for (int i = (usedSize-1-1)/2; i >= 0 ; i--) {
            heapifyDown(i);
        }
    }

//    向下调整堆
    private void heapifyDown(int parent) {
        int left = (2 * parent) + 1;
        int right = (2 * parent) + 2;
        int cur = parent;

        if (left < usedSize && elem[left] > elem[cur]){
            cur = left;
        }
        if (right < usedSize && elem[right] > elem[cur]){
            cur = right;
        }

        if (cur != parent){
            int temp = elem[parent];
            elem[parent] = elem[cur];
            elem[cur] = temp;

//            向下递归  此时 cur 为父节点
            heapifyDown(cur);
        }
    }

//    插入与删除元素复杂度是 logN
    public void insert(int val){
//      1.  首先判断是否已满
        if (usedSize == elem.length){
            elem = Arrays.copyOf(elem,2*elem.length); // 二倍扩容
        }
        elem[usedSize] = val;
//        添加到最后的位置 向上调整
        heapifyUp(usedSize);
        usedSize++;
    }

//    向上调整堆
    private void heapifyUp(int child){
//        传参是孩子节点的原因是 将新插入的节点放入到最后一个位置(这是孩子位置)
        int parent = (child - 1)/2;
//        当前节点与父节点比较大小 然后循环向上更新
        while(child > 0){
            if (elem[child] > elem[parent]){
                int temp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = temp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

//    如果采用向上建堆的方式 时间复杂度为N * log(N) 比用向下建堆慢很多 所以我们一般不用.


//    删除元素一定是删除堆顶元素  因为要实现优先级队列
    public void delete(){
        if (usedSize == 0){
            System.out.println("堆为空!");
           return;
        }
//        1.首先交换堆顶元素与最后一个元素
        int temp = elem[usedSize -1];
        elem[usedSize - 1] = elem[0];
        elem[0] = temp;

//        2.删除最后一个元素
        usedSize--;

//        3.向下调整堆
        heapifyDown(0);
    }

    // 堆排序方法
    public void heapSort(int[] arr) {
        elem = arr; // 将输入数组作为堆的存储
        usedSize = arr.length; // 初始化堆的大小

        // 1. 创建大根堆
        for (int i = (usedSize - 1 - 1) / 2; i >= 0; i--) {
            heapifyDown(i);
        }

        // 2. 交换堆顶元素与最后一个元素，并调整堆
        for (int i = usedSize - 1; i > 0; i--) {
            // 交换堆顶元素与最后一个元素
            int temp = elem[0];
            elem[0] = elem[i];
            elem[i] = temp;

            // 减小堆的大小，并调整堆
            usedSize--;
            heapifyDown(0);
        }
    }

}
